package com.mojito.learn.algorithm.datastructure;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @author liufq
 * @since 2022/4/11 下午6:55
 */
public class Head {

    /**
     * 通过最大堆解决大数据量的计算 TopN 问题
     */
    public static void main(String[] args) {
        // 创建最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        //往数组添加10万个数
        ArrayList<Integer> arrList = new ArrayList<>();
        for (int i = 0; i < 100000; i++) {
            arrList.add(i);
        }

        // 将数组数据顺序打乱
        Collections.shuffle(arrList);

        // 设置求最小的K个数
        int K = 10;

        // 往堆添加元素
        for (Integer value : arrList) {
            if (maxHeap.size() < K) {
                maxHeap.add(value);
            } else if (value < maxHeap.peek()) {
                // 找到更小的数value，则把它添加到堆
                maxHeap.remove();
                maxHeap.add(value);
            }
        }

        // 依次出堆顶， 取出最小的K个数
        while (!maxHeap.isEmpty()) {
            Integer poll = maxHeap.poll();
            System.out.println(poll);
        }
    }
}
